#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2021, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 0016.py
@time: 2021/9/14 15:26
@desc: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/submissions/
'''
class Solution:
    def numWays(self, n: int) -> int:
        if n==1 or n==0:
            return 1
        if n==2:
            return 2
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3,n):
            dp[i] = dp[i-1] + dp[i-2]

        return dp[n] % 1000000007

if __name__ == '__main__':
    sl = Solution()
    r = sl.numWays(3)
    print(r)